package com.ld.security.common.core.util;

import com.ld.security.common.core.base.column.ListString;
import com.ld.security.common.core.base.entity.ETreeEntity;

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class TreeUtil {


    /**
     * 深度优先构造书  自下向上构造
     * @param list
     * @param <E>
     * @return
     */
    public static <E extends ETreeEntity> List<E> dfsBuildTree(List<E> list){
        List<E> roots =new LinkedList<>();
        HashMap<String,E> map =  new HashMap<>();
        for (E e : list) {
            map.put(e.getId(),e);
        }
        for (E e : map.values()) {
            String parentId = e.getParentPath().getLast();
            E parent = map.get(parentId);
            if(parent != null){
                List<E> children =  parent.getChildren();
                if(children == null){
                    children =new LinkedList();
                    parent.setChildren(children);
                }
                children.add(e);
            }else{
                roots.add(e);
            }
        }

        return roots;
    }

    /**
     * 构造树路经
     * @param parent
     * @param <E>
     * @return
     */
    public static <E extends ETreeEntity> E buildTreePath(E parent) {
        List<E> children =  parent.getChildren();
        if(children != null){
            for (E child : children) {
                ListString parentPath =  new ListString(parent.getParentPath().getValue()+ETreeEntity.separator+parent.getId());
                child.setParentPath(parentPath);
                buildTreePath(child);
            }
        }
        return parent;
    }


    /**
     * 递归排序
     * @param list
     * @param c
     * @param <E>
     */
    public static <E extends ETreeEntity> List<E>  treeSort(List<E> list,Comparator<? super E> c) {
        if(list != null){
            list.sort(c);
            for (E e : list) {
                treeSort(e.getChildren(),c);
            }
        }
        return list;
    }
        /**
         * 构造树
         * @param list
         * @return
         */
    public static <E extends ETreeEntity> E buildTree(E parent, List<E> list){

        List<E> children =  new LinkedList<>();
        for (E y : list) {
            ListString listString =  y.getParentPath();
            String parentId =  listString.get(listString.size() - 1);
            if(parent.getId().equals(parentId)){
                children.add(y);
                buildTree(y,list);
            }
        }
        parent.setChildren(children);
        return parent;
    }


    /**
     * 树华为数组
     * @param tree
     * @param list
     * @param <E>
     * @return
     */
    public static <E extends ETreeEntity> void treeToLink(E tree,List<E> list) {
        list.add(tree);
        List<E> children =  tree.getChildren();
        if(children != null){
            for (E child : children) {
                treeToLink(child,list);
            }
        }

    }

    /**
     * 树华为数组
     * @param tree
     * @param <E>
     * @return
     */
    public static <E extends ETreeEntity> List<E> treeToLink(E tree) {
        List<E> list =  new LinkedList<>();
        treeToLink(tree,list);
        return  list;
    }


}
